home *** CD-ROM | disk | FTP | other *** search
/ Amiga Format CD 24 / Amiga Format AFCD24 (Feb 1998, Issue 108).iso / -in_the_mag- / emulation / amiga / uae-0.7.0b2 / src / gengenblitter.c < prev    next >
C/C++ Source or Header  |  1998-01-20  |  20KB  |  1,039 lines
  1.  /*
  2.   * UAE - The Un*x Amiga Emulator
  3.   *
  4.   * Optimized blitter minterm function generator
  5.   *
  6.   * Copyright 1995,1996 Bernd Schmidt
  7.   * Copyright 1996 Alessandro Bissacco
  8.   *
  9.   * Overkill, n: cf. genblitter
  10.   */
  11.  
  12. #include "sysconfig.h"
  13. #include "sysdeps.h"
  14.  
  15. #include "config.h"
  16. #include "options.h"
  17.  
  18. static void nop(int);
  19.  
  20. #if 0
  21. typedef struct alloc_hdr
  22. {
  23.     int size;
  24.     struct alloc_hdr *next, *prev;
  25.     void *from, *from2;
  26. } *ahead;
  27.  
  28. static struct alloc_hdr ah_top = { 0, &ah_top, &ah_top, 0, 0 };
  29.  
  30. int nbytesmalloced = 0;
  31. int malloc_cnt = 0;
  32.  
  33. static void *xmalloc(int sz)
  34. {
  35.     ahead mem = (ahead)malloc(sz + sizeof(struct alloc_hdr));
  36.     mem->size = sz;
  37.     mem->next = &ah_top;
  38.     mem->prev = ah_top.prev;
  39.     ah_top.prev->next = mem;
  40.     ah_top.prev = mem;
  41.  
  42.     mem->from = __builtin_return_address(0);
  43.     mem->from2 = __builtin_return_address(1);
  44.  
  45.     malloc_cnt++;
  46.     nbytesmalloced += sz;
  47.  
  48.     return mem + 1;
  49. }
  50.  
  51. static void *xrealloc(void *mem, int sz)
  52. {
  53.     if (mem == NULL)
  54.     return xmalloc(sz);
  55.     else {
  56.     ahead m = (ahead)mem;
  57.     m--;
  58.  
  59.     nbytesmalloced += sz - m->size;
  60.     m->size = sz;
  61.     return ((ahead)realloc(m, sz + sizeof(struct alloc_hdr))) + 1;
  62.     }
  63. }
  64.  
  65. static void xfree(void *mem)
  66. {
  67.     ahead m = (ahead)mem;
  68.  
  69.     m--;
  70.  
  71.     m->next->prev = m->prev;
  72.     m->prev->next = m->next;
  73.     nbytesmalloced -= m->size;
  74.     malloc_cnt--;
  75.     free(m);
  76. }
  77. #else
  78. #define xmalloc malloc
  79. #define xfree free
  80. #define xrealloc realloc
  81. #endif
  82.  
  83. typedef struct tree_n {
  84.     enum tree_op { op_and, op_or, op_xor, op_not, op_a, op_b, op_c } op;
  85.     struct tree_n *left, *right;
  86. } *tree;
  87.  
  88. static struct tree_n TRA = { op_a, NULL, NULL }, TRB = { op_b, NULL, NULL }, TRC = { op_c, NULL, NULL };
  89. static tree tree_a = &TRA, tree_b = &TRB, tree_c = &TRC;
  90.  
  91. typedef struct {
  92.     tree *trees;
  93.     int space;
  94.     int ntrees;
  95. } tree_vec;
  96.  
  97. static tree best_tree, main_tree;
  98. static int best_cost = 65535;
  99.  
  100. static void kill_tree(tree *t)
  101. {
  102.     if (*t != NULL && *t != tree_a && *t != tree_b && *t != tree_c) {
  103.     if ((*t)->left) kill_tree(&(*t)->left);
  104.     if ((*t)->right) kill_tree(&(*t)->right);
  105.     xfree(*t);
  106.     }
  107.     *t = NULL;
  108. }
  109.  
  110. static tree dup_tree(tree t)
  111. {
  112.     if (t == NULL || t == tree_a || t == tree_b || t == tree_c)
  113.     return t;
  114.     else {
  115.     tree nt = (tree)xmalloc(sizeof(struct tree_n));
  116.     nt->op = t->op;
  117.     nt->left = dup_tree(t->left);
  118.     nt->right = dup_tree(t->right);
  119.     return nt;
  120.     }
  121. }
  122.  
  123. static tree new_op_tree(enum tree_op op, tree l, tree r)
  124. {
  125.     tree t;
  126.     if (op == op_not && l->op == op_not) {
  127.     t = l->left;
  128.     xfree(l);
  129.     return t;
  130.     }
  131.     t = (tree)xmalloc(sizeof(struct tree_n));
  132.     t->left = l;
  133.     t->right = r;
  134.     t->op = op;
  135.     return t;
  136. }
  137.  
  138. static int tree_cst(tree t, int *nota, int *notb, int *notc)
  139. {
  140.     switch(t->op) {
  141.      case op_a:
  142.      case op_b:
  143.      case op_c:
  144.     return 0;
  145.      case op_not:
  146.     switch (t->left->op) {
  147.      case op_a:
  148.         if (*nota)
  149.         return 0;
  150.         *nota = 1;
  151.         return 4;
  152.  
  153.      case op_b:
  154.         if (*notb)
  155.         return 0;
  156.         *notb = 1;
  157.         return 4;
  158.  
  159.      case op_c:
  160.         if (*notc)
  161.         return 0;
  162.         *notc = 1;
  163.         return 4;
  164. #if 0
  165.      case op_not:
  166.         return tree_cst(t->left->left, nota, notb, notc);
  167. #endif
  168.      default:
  169.         break;
  170.     }
  171.     return 3 + tree_cst(t->left, nota, notb, notc);
  172.  
  173.      case op_and:
  174.      case op_xor:
  175.      case op_or:
  176.     return 3 + tree_cst(t->left, nota, notb, notc) + tree_cst(t->right, nota, notb, notc);
  177.     }
  178.     return 0;
  179. }
  180.  
  181. static int tree_cost(tree t)
  182. {
  183.     int a = 0,b = 0,c = 0;
  184.  
  185.     return tree_cst(t,&a,&b,&c);
  186. }
  187.  
  188. static int eval(tree t)
  189. {
  190.     int v = tree_cost(t);
  191.     if (v < best_cost) {
  192.     best_cost = v;
  193.     if (best_tree != NULL)
  194.         kill_tree(&best_tree);
  195.     best_tree = dup_tree(t);
  196.     }
  197.     return v;
  198. }
  199.  
  200. static int tree_equal(tree a, tree b)
  201. {
  202.     unsigned long mask = 0;
  203.     int i;
  204.     tree t2, t3;
  205.  
  206.     if (a == b)
  207.     return 1;
  208.     if (a->op != b->op)
  209.     return 0;
  210.     if (a->op == op_not)
  211.     return tree_equal(a->left, b->left);
  212.  
  213.     if (a->op != op_xor && a->op != op_or && a->op != op_and)
  214.     return 0;
  215.  
  216.     if (tree_equal(a->left, b->left))
  217.     return tree_equal(a->right, b->right);
  218.  
  219.     for (i = 0, t2 = a; t2->op == a->op; t2 = t2->right, i++)
  220.     ;
  221.     for (t3 = b; t3->op == b->op; t3 = t3->right, i--)
  222.     ;
  223.  
  224.     if (i != 0)
  225.     return 0;
  226.  
  227.     t2 = a;
  228.     for (;;) {
  229.     tree ttmp;
  230.     tree t3;
  231.  
  232.     if (t2->op == a->op)
  233.         ttmp = t2->left;
  234.     else
  235.         ttmp = t2;
  236.  
  237.     t3 = b;
  238.     for (i = 0;; i++) {
  239.         tree ttmp2;
  240.  
  241.         if (t3->op == b->op)
  242.         ttmp2 = t3->left;
  243.         else
  244.         ttmp2 = t3;
  245.  
  246.         if ((mask & (1 << i)) == 0 && tree_equal(ttmp, ttmp2)) {
  247.         mask |= 1 << i;
  248.         break;
  249.         }
  250.  
  251.         if (t3->op != b->op)
  252.         return 0;
  253.  
  254.         t3 = t3->right;
  255.     }
  256.  
  257.     if (t2->op != a->op)
  258.         break;
  259.  
  260.     t2 = t2->right;
  261.     }
  262.     return 1;
  263. }
  264.  
  265. static int tree_isnormal(tree t)
  266. {
  267.     if ((t->op == op_xor || t->op == op_and || t->op == op_or)
  268.     && t->left->op == t->op)
  269.     return 0;
  270.     return 1;
  271. }
  272.  
  273. static void normalize(tree *t)
  274. {
  275.     if (*t == NULL)
  276.     return;
  277.  
  278.     if ((*t)->op == op_not && (*t)->left->op == op_not) {
  279.     tree t2 = (*t)->left->left;
  280.     xfree((*t)->left);
  281.     xfree(*t);
  282.     *t = t2;
  283.     }
  284.  
  285.     while (((*t)->op == op_xor || (*t)->op == op_and || (*t)->op == op_or)
  286.     && (*t)->left->op == (*t)->op)
  287.     {
  288.     tree tmp = (*t)->left->left;
  289.     (*t)->left->left = (*t)->left->right;
  290.     (*t)->left->right = (*t)->right;
  291.     (*t)->right = (*t)->left;
  292.     (*t)->left = tmp;
  293.     }
  294.     normalize(&(*t)->left);
  295.     normalize(&(*t)->right);
  296. }
  297.  
  298. static void add_vec(tree_vec *tv, tree t)
  299. {
  300.     if (!tree_isnormal(t))
  301.     nop(2);
  302.  
  303.     if (tv == NULL) {
  304.     eval(t);
  305.     kill_tree(&t);
  306.     } else {
  307.     int i;
  308.     for (i = 0; i < tv->ntrees; i++)
  309.         if (tree_equal(tv->trees[i], t)) {
  310.         kill_tree(&t);
  311.         return;
  312.         }
  313.  
  314.     if (tv->ntrees == tv->space) {
  315.         tv->trees = (tree *)xrealloc(tv->trees, sizeof(tree)*(tv->space += 40));
  316.     }
  317.     tv->trees[tv->ntrees++] = t;
  318.     }
  319. }
  320.  
  321. static void kill_vec(tree_vec *tv)
  322. {
  323.     int i;
  324.     for (i = 0; i < tv->ntrees; i++)
  325.     kill_tree(tv->trees + i);
  326.     xfree(tv->trees);
  327. }
  328.  
  329. static void init_vec(tree_vec *tv)
  330. {
  331.     tv->ntrees = tv->space = 0;
  332.     tv->trees = NULL;
  333. }
  334.  
  335. static void do_sprint_tree(char *s, tree *t)
  336. {
  337.     switch ((*t)->op) {
  338.      case op_a:
  339.     strcat(s, "srca");
  340.     break;
  341.      case op_b:
  342.     strcat(s, "srcb");
  343.     break;
  344.      case op_c:
  345.     strcat(s, "srcc");
  346.     break;
  347.  
  348.      case op_and:
  349.     strcat(s, "(");
  350.     do_sprint_tree(s, &(*t)->left);
  351.     strcat(s, " & ");
  352.     while ((*t)->right->op == op_and) {
  353.         t = &(*t)->right;
  354.         do_sprint_tree(s, &(*t)->left);
  355.         strcat(s, " & ");
  356.     }
  357.     do_sprint_tree(s, &(*t)->right);
  358.     strcat(s, ")");
  359.     break;
  360.  
  361.      case op_or:
  362.     strcat(s, "(");
  363.     do_sprint_tree(s, &(*t)->left);
  364.     strcat(s, " | ");
  365.     while ((*t)->right->op == op_or) {
  366.         t = &(*t)->right;
  367.         do_sprint_tree(s, &(*t)->left);
  368.         strcat(s, " | ");
  369.     }
  370.     do_sprint_tree(s, &(*t)->right);
  371.     strcat(s, ")");
  372.     break;
  373.  
  374.      case op_xor:
  375.     strcat(s, "(");
  376.     do_sprint_tree(s, &(*t)->left);
  377.     strcat(s, " ^ ");
  378.     while ((*t)->right->op == op_xor) {
  379.         t = &(*t)->right;
  380.         do_sprint_tree(s, &(*t)->left);
  381.         strcat(s, " ^ ");
  382.     }
  383.     do_sprint_tree(s, &(*t)->right);
  384.     strcat(s, ")");
  385.     break;
  386.  
  387.      case op_not:
  388.     strcat(s, "~");
  389.     do_sprint_tree(s,&(*t)->left);
  390.     break;
  391.     }
  392. }
  393.  
  394. static void sprint_tree(char *s, tree t)
  395. {
  396.     tree tt = dup_tree(t);
  397.     *s = 0;
  398.     do_sprint_tree(s, &tt);
  399.     kill_tree(&tt);
  400. }
  401.  
  402. static int treecmp(tree a, tree b)
  403. {
  404.     if (b->op != a->op)
  405.     return 1;
  406.  
  407.     if (a == b)
  408.     return 0;
  409.  
  410.     if (a->op == op_not)
  411.     return treecmp(a->left, b->left);
  412.  
  413.     return 1;
  414. }
  415.  
  416. static int issrc(tree t)
  417. {
  418.     return t->op == op_a || t->op == op_b || t->op == op_c;
  419. }
  420.  
  421. static void do_opt(tree, tree_vec *, int);
  422. static void opt_xor(tree t, tree_vec *tv);
  423. static void opt_distrib(tree t, tree_vec *tv);
  424. static void opt_demorgan(tree t, tree_vec *tv);
  425.  
  426. static void opt_not(tree_vec *tv_dst, tree_vec *tv_src)
  427. {
  428.     int i;
  429.     for (i = 0; i < tv_src->ntrees; i++) {
  430.     tree t = tv_src->trees[i];
  431.  
  432.     add_vec(tv_dst, new_op_tree(op_not, dup_tree(t), NULL));
  433.     }
  434. }
  435.  
  436. static void demorgan(tree t, tree_vec *tv)
  437. {
  438.     tree newt = NULL, t_l = NULL;
  439.     int neednot = 0;
  440.  
  441.     if (t->op == op_not && (t->left->op == op_and || t->left->op == op_or))
  442.     t_l = dup_tree(t->left);
  443.     else if (t->op == op_and || t->op == op_or)
  444.     t_l = dup_tree(t), neednot = 1;
  445.     else
  446.     return;
  447.  
  448.     if (t_l->op == op_and)
  449.     t_l->op = op_or;
  450.     else
  451.     t_l->op = op_and;
  452.  
  453.     t_l->left = new_op_tree(op_not, t_l->left, NULL);
  454.     t_l->right = new_op_tree(op_not, t_l->right, NULL);
  455.     normalize(&t_l);
  456.  
  457.     if (neednot) {
  458.     tree_vec tv2;
  459.     int i;
  460.  
  461.     init_vec(&tv2);
  462.     opt_xor(t_l, &tv2);
  463.     opt_distrib(t_l, &tv2);
  464.     add_vec(&tv2, t_l);
  465. #if 0
  466.     for (i = 0; i < tv2.ntrees; i++) {
  467.         add_vec(tv, new_op_tree(op_not, dup_tree(tv2.trees[i]), NULL));
  468.     }
  469. #endif
  470.     opt_not(tv, &tv2);
  471.     kill_vec(&tv2);
  472.     } else {
  473.     opt_xor(t_l, tv);
  474.     opt_distrib(t_l, tv);
  475.     add_vec(tv, t_l);
  476.     }
  477. }
  478.  
  479. static void opt_xor(tree t, tree_vec *tv)
  480. {
  481.     tree_vec tv1, tv2;
  482.     tree tt1, tt2;
  483.     int i;
  484.  
  485.     enum tree_op top, sop;
  486.     tree t1, t2, t3;
  487.     int n1 = 0, n2 = 0, ok1 = 0, ok2 = 0;
  488.  
  489.     top = t->op;
  490.     if (top != op_or)
  491.     return;
  492.  
  493.     sop = t->left->op;
  494.     if (sop != op_and || t->right->op != sop)
  495.     return;
  496.  
  497.     if (t->left->left->op == op_not) {
  498.     n1 = 1;
  499.     t1 = t->left->left->left;
  500.     } else {
  501.     t1 = t->left->left;
  502.     }
  503.  
  504.     if (t->left->right->op == op_not) {
  505.     n2 = 1;
  506.     t2 = t->left->right->left;
  507.     } else {
  508.     t2 = t->left->right;
  509.     }
  510.  
  511.     if (t->right->left->op == op_not) {
  512.     if (n1 == 0 && tree_equal(t->right->left->left, t1))
  513.         ok1++;
  514.     if (n2 == 0 && tree_equal(t->right->left->left, t2))
  515.         ok2++;
  516.     } else {
  517.     if (n1 == 1 && tree_equal(t->right->left, t1))
  518.         ok1++;
  519.     if (n2 == 1 && tree_equal(t->right->left, t2))
  520.         ok2++;
  521.     }
  522.  
  523.     if (t->right->right->op == op_not) {
  524.     if (n1 == 0 && tree_equal(t->right->right->left, t1))
  525.         ok1++;
  526.     if (n2 == 0 && tree_equal(t->right->right->left, t2))
  527.         ok2++;
  528.     } else {
  529.     if (n1 == 1 && tree_equal(t->right->right, t1))
  530.         ok1++;
  531.     if (n2 == 1 && tree_equal(t->right->right, t2))
  532.         ok2++;
  533.     }
  534.  
  535.     if (ok1 != 1 || ok2 != 1)
  536.     return;
  537.  
  538.     t3 = new_op_tree(op_xor, dup_tree(t1), dup_tree(t2));
  539.     if (n1 == n2)
  540.     t3 = new_op_tree(op_not, t3, NULL);
  541.     normalize(&t3);
  542.     add_vec(tv, t3);
  543.  
  544.     init_vec(&tv1); init_vec(&tv2);
  545.     tt1 = new_op_tree(op_not, dup_tree(t1), NULL);
  546.     tt2 = new_op_tree(op_not, dup_tree(t2), NULL);
  547.  
  548.     do_opt(tt1, &tv1, 0); do_opt(tt2, &tv2, 0);
  549.     kill_tree(&tt1); kill_tree(&tt2);
  550.  
  551.     for (i = 0; i < tv1.ntrees; i++) {
  552.     t3 = new_op_tree(op_xor, dup_tree(tv1.trees[i]), dup_tree(t2));
  553.     if (n1 != n2)
  554.         t3 = new_op_tree(op_not, t3, NULL);
  555.     normalize(&t3);
  556.     add_vec(tv, t3);
  557.     }
  558.  
  559.     for (i = 0; i < tv2.ntrees; i++) {
  560.     t3 = new_op_tree(op_xor, dup_tree(t1), dup_tree(tv2.trees[i]));
  561.     if (n1 != n2)
  562.         t3 = new_op_tree(op_not, t3, NULL);
  563.     normalize(&t3);
  564.     add_vec(tv, t3);
  565.     }
  566.  
  567.     for (i = 0; i < tv1.ntrees; i++) {
  568.     int j;
  569.  
  570.     for (j = 0; j < tv2.ntrees; j++) {
  571.         t3 = new_op_tree(op_xor, dup_tree(tv1.trees[i]), dup_tree(tv2.trees[j]));
  572.         if (n1 == n2)
  573.         t3 = new_op_tree(op_not, t3, NULL);
  574.         normalize(&t3);
  575.         add_vec(tv, t3);
  576.     }
  577.     }
  578.  
  579.     kill_vec(&tv1); kill_vec(&tv2);
  580. }
  581.  
  582. static tree opt_factor_tree(tree old, tree f, enum tree_op top, enum tree_op sop,
  583.                 tree *remainder)
  584. {
  585.     tree t1 = old;
  586.     tree t2 = NULL;
  587.     *remainder = NULL;
  588.  
  589.     for (;;) {
  590.     int found_factor = 0;
  591.     tree t3 = NULL;
  592.     tree t4;
  593.  
  594.     if (t1->op == top)
  595.         t4 = t1->left;
  596.     else
  597.         t4 = t1;
  598.  
  599.     if (t4->op != sop) {
  600.         if (*remainder == NULL)
  601.         *remainder = dup_tree(t4);
  602.         else
  603.         *remainder = new_op_tree(top, *remainder, dup_tree(t4));
  604.     } else {
  605.         for (;;) {
  606.         tree t5;
  607.  
  608.         if (t4->op == sop)
  609.             t5 = t4->left;
  610.         else
  611.             t5 = t4;
  612.  
  613.         if (treecmp(t5, f) != 0) {
  614.             if (t3 == NULL)
  615.             t3 = dup_tree(t5);
  616.             else
  617.             t3 = new_op_tree(sop, t3, dup_tree(t5));
  618.         } else
  619.             found_factor = 1;
  620.  
  621.         if (t4->op != sop)
  622.             break;
  623.         t4 = t4->right;
  624.         }
  625.         if (!found_factor) {
  626.         if (*remainder == NULL)
  627.             *remainder = t3;
  628.         else
  629.             *remainder = new_op_tree(top, *remainder, t3);
  630.         } else {
  631.         if (t2 == NULL)
  632.             t2 = t3;
  633.         else
  634.             t2 = new_op_tree(top, t2, t3);
  635.         }
  636.     }
  637.  
  638.     if (t1->op != top)
  639.         break;
  640.  
  641.     t1 = t1->right;
  642.     }
  643.     if (t2 == NULL || t2->op != top) {
  644.     if (*remainder != NULL)
  645.         kill_tree(remainder);
  646.     if (t2 != NULL)
  647.         kill_tree(&t2);
  648.     return NULL;
  649.     }
  650.     return t2;
  651. }
  652.  
  653. static void opt_distrib(tree t, tree_vec *tv)
  654. {
  655.     enum tree_op top, sop;
  656.     tree t1;
  657.  
  658.     top = t->op;
  659.  
  660.     if (top != op_and && top != op_or)
  661.     return;
  662.  
  663.     sop = t->left->op;
  664.     if ((top == op_and && sop != op_or) || (top == op_or && sop != op_and))
  665.     return;
  666. #if 0
  667.     t1 = t->right;
  668.     for (;;) {
  669.     if (t1->op == sop)
  670.         break;
  671.     if (t1->op != top)
  672.         return;
  673.     if (t1->left->op != sop)
  674.         return;
  675.     t1 = t1->right;
  676.     }
  677. #endif
  678.  
  679.     t1 = t->left;
  680.     for (;;) {
  681.     tree t3, t4, t5;
  682.  
  683.     if (t1->op == sop)
  684.         t3 = t1->left;
  685.     else
  686.         t3 = t1;
  687.  
  688.     t4 = opt_factor_tree(t, t3, top, sop, &t5);
  689.     if (t4 != NULL) {
  690.         tree_vec tv2;
  691.         int i;
  692.  
  693.         init_vec(&tv2);
  694.         normalize(&t4);
  695.         do_opt(t4, &tv2, 0);
  696.         kill_tree(&t4);
  697.  
  698.         for (i = 0; i < tv2.ntrees; i++) {
  699.         t4 = new_op_tree(sop, dup_tree(t3), dup_tree(tv2.trees[i]));
  700.         if (t5 != NULL)
  701.             t4 = new_op_tree(top, t4, dup_tree(t5));
  702.         normalize(&t4);
  703.         if (t5 != NULL) {
  704.             demorgan(t4, tv);
  705.             opt_xor(t4, tv);
  706.         }
  707.         add_vec(tv, t4);
  708.         }
  709.         kill_vec(&tv2);
  710.  
  711.         if (t5 != NULL)
  712.         kill_tree(&t5);
  713.     }
  714.     if (t1->op != sop)
  715.         break;
  716.     t1 = t1->right;
  717.     }
  718. }
  719.  
  720. struct perm_data {
  721.     int n;
  722.     int *a;
  723.     tree_vec *tvar;
  724.     tree_vec *tvparent;
  725.     enum tree_op op;
  726.     int neednot;
  727.     int didmorgan;
  728. };
  729.  
  730. static void allperms(struct perm_data *pd, int p,
  731.              void (*f)(struct perm_data *))
  732. {
  733.     if (p == pd->n)
  734.     f(pd);
  735.     else {
  736.     int i;
  737.     for (i = p; i < pd->n; i++) {
  738.         int tmp = pd->a[i];
  739.         pd->a[i] = pd->a[p];
  740.         pd->a[p] = tmp;
  741.         allperms(pd, p + 1, f);
  742.         tmp = pd->a[i];
  743.         pd->a[i] = pd->a[p];
  744.         pd->a[p] = tmp;
  745.     }
  746.     }
  747.  
  748. }
  749.  
  750. static void optimize(tree_vec *tv, tree subt, enum tree_op top)
  751. {
  752.     tree_vec sub_tv;
  753.     int i;
  754.  
  755.     if (subt->op != top) {
  756.     add_vec(tv, dup_tree(subt));
  757.     return;
  758.     }
  759.  
  760.     init_vec(&sub_tv);
  761.     optimize(&sub_tv, subt->right, top);
  762.  
  763.     for (i = 0; i < sub_tv.ntrees; i++) {
  764.     tree t1 = new_op_tree(top, dup_tree(subt->left), dup_tree(sub_tv.trees[i]));
  765.     demorgan(t1, tv);
  766.     opt_xor(t1, tv);
  767.     opt_distrib(t1, tv);
  768.     add_vec(tv, t1);
  769.     }
  770.     kill_vec(&sub_tv);
  771. }
  772.  
  773. static void do_opt_perm_1(struct perm_data *pd, int i, tree rhs)
  774. {
  775.     int j = pd->a[i];
  776.     int k;
  777.  
  778.     i++;
  779.     for (k = 0; k < pd->tvar[j].ntrees; k++) {
  780.     tree lhs;
  781.  
  782.     if (rhs == NULL)
  783.         lhs = dup_tree(pd->tvar[j].trees[k]);
  784.     else
  785.         lhs = new_op_tree(pd->op, dup_tree(pd->tvar[j].trees[k]), dup_tree(rhs));
  786.  
  787.     if (i < pd->n) {
  788.         do_opt_perm_1(pd, i, lhs);
  789.     } else {
  790.         normalize(&lhs);
  791.  
  792.         if (pd->neednot) {
  793.         int i;
  794.         tree_vec tvs;
  795.         init_vec(&tvs);
  796.  
  797.         optimize(&tvs, lhs, lhs->op);
  798. #if 0
  799.         for (i = 0; i < tvs.ntrees; i++)
  800.             add_vec(pd->tvparent, new_op_tree(op_not, dup_tree(tvs.trees[i]), NULL));
  801. #endif
  802.         opt_not(pd->tvparent, &tvs);
  803.         kill_vec(&tvs);
  804.         } else
  805.         optimize(pd->tvparent, lhs, lhs->op);
  806.     }
  807.  
  808.     kill_tree(&lhs);
  809.     }
  810.     nop(j);
  811. }
  812.  
  813. void nop(int a)
  814. {
  815. }
  816.  
  817. static void do_opt_perm(struct perm_data *pd)
  818. {
  819.     do_opt_perm_1(pd, 0, NULL);
  820. }
  821.  
  822. static void do_opt(tree t, tree_vec *tv, int did_morgan)
  823. {
  824. /*    if (!did_morgan)
  825.     demorgan(t, tv);
  826.     opt_distrib(t, tv);
  827.     opt_xor(t, tv);*/
  828.  
  829.     if ((t->op == op_and || t->op == op_or)
  830.     || (t->op == op_not
  831.         && (t->left->op == op_and || t->left->op == op_or)))
  832.     {
  833.     int i, j;
  834.     struct perm_data pd;
  835.     tree t2, t3;
  836.     int neednot = t->op == op_not;
  837.  
  838.     if (neednot)
  839.         t3 = t->left;
  840.     else
  841.         t3 = t;
  842.  
  843.     pd.didmorgan = did_morgan;
  844.     pd.op = t3->op;
  845.     pd.neednot = neednot;
  846.     pd.tvparent = tv;
  847.     pd.n = 2;
  848.  
  849.     t2 = t3->right;
  850.     while (t2->op == t3->op) {
  851.         pd.n++;
  852.         t2 = t2->right;
  853.     }
  854.  
  855.     pd.a = (int *)xmalloc(sizeof(int)*pd.n);
  856.     pd.tvar = (tree_vec *)xmalloc(sizeof(tree_vec)*pd.n);
  857.     for (i = 0; i < pd.n; i++)
  858.         pd.a[i] = i;
  859.  
  860.     t2 = t3; i = 0;
  861.     while (t2->op == t3->op) {
  862.         init_vec(pd.tvar + i);
  863.         do_opt(t2->left, pd.tvar + i, neednot && did_morgan);
  864.         t2 = t2->right;
  865.         i++;
  866.     }
  867.     init_vec(pd.tvar + i);
  868.     do_opt(t2, pd.tvar + i, 0);
  869.  
  870.     allperms(&pd, 0, do_opt_perm);
  871.  
  872.     for (i = 0; i < pd.n; i++) {
  873.         kill_vec(pd.tvar + i);
  874.     }
  875.     xfree(pd.tvar);
  876.     xfree(pd.a);
  877.     } else {
  878.     demorgan(t, tv);
  879.     opt_xor(t, tv);
  880.     opt_distrib(t, tv);
  881.     add_vec(tv, dup_tree(t));
  882.     }
  883. }
  884.  
  885. static int bitset(int mt, int bit)
  886. {
  887.     return mt & (1 << bit);
  888. }
  889.  
  890. static char buffer[4096];
  891.  
  892. static int generate_expr(int minterm, int print)
  893. {
  894.     int result = 0;
  895.     int firstor = 1;
  896.     int bits = 0;
  897.     int i;
  898.     int expr_bit[8], expr_dc[8], nexp = 0;
  899.     int expr_used[8];
  900.     tree t, t1 = NULL;
  901.  
  902.     if (minterm == 0) {
  903.     if (print)
  904.         printf("0");
  905.     return 0;
  906.     }
  907.     if (minterm == 0xFF) {
  908.     if (print)
  909.         printf("0xFFFFFFFF");
  910.     return 0;
  911.     }
  912.  
  913.     for(i=0; i<8; i++) {
  914.     if (bitset(minterm, i) && !bitset(bits,i)) {
  915.         int j;
  916.         int dontcare = 0;
  917.         int firstand = 1;
  918.         int bitbucket[8], bitcount;
  919.  
  920.         bits |= 1<<i;
  921.         bitcount = 1; bitbucket[0] = i;
  922.         for(j=1; j<8; j *= 2) {
  923.         int success = 1;
  924.         int k;
  925.         for(k=0; k < bitcount; k++) {
  926.             if (!bitset(minterm, bitbucket[k] ^ j)) {
  927.             success = 0;
  928.             }
  929.         }
  930.         if (success) {
  931.             int l;
  932.             dontcare |= j;
  933.             for(l=bitcount; l < bitcount*2; l++) {
  934.             bitbucket[l] = bitbucket[l-bitcount] ^ j;
  935.             bits |= 1 << bitbucket[l];
  936.             }
  937.             bitcount *= 2;
  938.         }
  939.         }
  940.         expr_used[nexp] = 1;
  941.         expr_dc[nexp] = dontcare;
  942.         expr_bit[nexp++] = i;
  943.     }
  944.     }
  945.  
  946.     t1 = NULL;
  947.     for (i = 0; i < nexp; i++) {
  948.     int j, firstand = 1;
  949.     tree t2 = NULL;
  950.  
  951.     for (j = 1; j < 8; j *= 2) {
  952.         if (!(expr_dc[i] & j)) {
  953.         tree t3 = j == 1 ? tree_c : j == 2 ? tree_b : tree_a;
  954.  
  955.         if ((expr_bit[i] & j) == 0)
  956.             t3 = new_op_tree(op_not, t3, NULL);
  957.  
  958.         if (t2 != NULL)
  959.             t2 = new_op_tree(op_and, t3, t2);
  960.         else
  961.             t2 = t3;
  962.         result |= (j == 1 ? 4 : j == 2 ? 2 : 1);
  963.         }
  964.     }
  965.     if (t1 != NULL)
  966.         t1 = new_op_tree(op_or, t2, t1);
  967.     else
  968.         t1 = t2;
  969.     }
  970.     if (t1 != NULL) {
  971.     best_tree = NULL;
  972.     best_cost = 65535;
  973.     normalize(&t1);
  974.     main_tree = t1;
  975.     do_opt(main_tree, NULL, 0);
  976.     sprint_tree(buffer, best_tree);
  977.     printf("%s", buffer);
  978.     kill_tree(&main_tree);
  979.     kill_tree(&best_tree);
  980.     }
  981.  
  982.     return result;
  983. }
  984.  
  985. static void print_expr(int minterm)
  986. {
  987.     generate_expr(minterm, 1);
  988.     printf("\n");
  989. }
  990.  
  991. static void print_tree(tree t)
  992. {
  993.     char buf[32768];
  994.  
  995.     sprint_tree(buf, t);
  996.     printf("%s\n", buf);
  997. }
  998.  
  999. static void generate_optable(void)
  1000. {
  1001.     int minterm;
  1002.     printf(" /* This file generated automatically - do not edit */\n\n");
  1003.     printf("#include \"genblitter.h\"\n\n");
  1004.     printf("struct blitop blitops[256] = {\n");
  1005.     for (minterm = 0; minterm < 256; minterm++) {
  1006.     int r;
  1007.     printf(" /* %02x */  { \"", minterm);
  1008.     r = generate_expr(minterm, 1);
  1009.     printf("\", %d }%s\n", r, minterm == 255 ? "" : ",");
  1010.     fflush(stdout);
  1011.     }
  1012.     printf("};\n");
  1013. }
  1014.  
  1015. int main(int argc, char **argv)
  1016. {
  1017. #if 0
  1018.     tree t, t1, t2, t3;
  1019.     tree_vec tv1;
  1020.     int i;
  1021.  
  1022.     t1 = new_op_tree(op_or, tree_b, tree_a);
  1023.     t2 = new_op_tree(op_or, tree_c, tree_a);
  1024.     t3 = new_op_tree(op_not, new_op_tree(op_xor, tree_c, tree_b), NULL);
  1025.  
  1026.     t = new_op_tree(op_and, t1, new_op_tree(op_and, t2, t3));
  1027.     init_vec(&tv1);
  1028.  
  1029.     opt_distrib(t, &tv1);
  1030.     for (i = 0; i < tv1.ntrees; i++)
  1031.     print_tree(tv1.trees[i]);
  1032.     kill_vec(&tv1);
  1033. #endif
  1034.     generate_optable();
  1035.  
  1036.     return 0;
  1037. }
  1038.  
  1039.